package com.learning.lesson05kmp;

import java.util.Arrays;

/**
 * 字符串匹配-KMP算法
 *
 * @author Zongheng Ma
 * @date 2020/11/16
 */
public class KmpAlgorithm {

    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "AB ";
        System.out.println(Arrays.toString(kmpNext(str2)));
        System.out.println("index = " + kmpMatch(str1, str2));
    }


    /**
     * KMP匹配
     *
     * @param str1 父串
     * @param str2 模式串
     * @return 模式串在父串中首次出现的位置
     */
    public static int kmpMatch(String str1, String str2) {
        // 获取模式串的部分匹配表
        int[] next = kmpNext(str2);

        // 遍历匹配
        for (int i = 0, j = 0; i < str1.length(); i++) {
            /*while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }*/

            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            } else {
                i = i - j + next[j];
                j = 0;
            }
            if (j == str2.length()) {
                return i - j + 1;
            }
        }

        // 未全部匹配，返回-1
        return -1;
    }


    /**
     * 获取部分匹配表（next数组）
     *
     * @param str 模式串
     * @return
     */
    public static int[] kmpNext(String str) {
        // 创建next数组
        int[] next = new int[str.length()];
        // 长度为一的字符串，其前后缀均为空集，前后缀共有子串也是空集，故部分匹配值也是0
        next[0] = 0;
        // 当前字符串的长度大于1
        for (int i = 1, j = 0; i < str.length(); i++) {

            while (j > 0 && str.charAt(i) != str.charAt(j)) {
                j = next[j - 1];
            }

            if (str.charAt(i) == str.charAt(j)) {
                // 前缀和后缀匹配
                j++;
            } /*else {
                // 前缀和后缀不匹配
                j = 0;
            }*/
            next[i] = j;
        }
        return next;
    }
}
